E (complessità)

Nella teoria della complessità computazionale, la classe di complessità E è l'insieme di problemi decisionali che possono essere risolti da una macchina deterministica di Turing nel tempo 2^O(n) ed è perciò uguale alla classe di complessità DTIME(2^O(n)).

E, diversamente dalla classe simile EXPTIME, non è chiuso sotto le riduzioni molti a uno in tempo polinomiale.

Bibliografia[modifica | modifica wikitesto]

E. Allender e M. Strauss, Measure on small complexity classes with applications for BPP, in Proceedings of IEEE FOCS'94, 1994, pp. 807–818, ECCC TR 94-004, DIMACS TR 94-18.
R. Book, On languages accepted in polynomial time, in SIAM Journal on Computing, vol. 1, n. 4, 1972, pp. 281–287.
R. Book, Comparing complexity classes, in Journal of Computer and System Sciences, vol. 3, n. 9, 1974, pp. 213–229.
R. Impagliazzo e G. Tardos, Decision versus search problems in super-polynomial time, in Proceedings of IEEE FOCS 1989, 1989, pp. 222–227.
O. Watanabe, Comparison of polynomial time completeness notions, in Theoretical Computer Science, vol. 53, 1987, pp. 249–265.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica